"""
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/tencent/xxzqki/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        size = len(strs)
        res = list(strs[0])
        for i in range(1, size):
            n = len(res)
            m = len(strs[i])
            if n == 0:
                break
            for j in range(n):
                if j == m or res[j] != strs[i][j]:
                    res = res[:j]
                    break
        return "".join(res)

    def longestCommonPrefix2(self, strs: List[str]) -> str:
        if not strs:
            return ""
        str0 = min(strs)
        str1 = max(strs)
        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0


if __name__ == '__main__':
    l = ["flower","flow","flight"]
    sol = Solution()
    print(sol.longestCommonPrefix(l))
